Object tracking has several important applications for users of computing devices, such as personal computers, tablets, smartphones, or head-mounted displays and other wearable computing devices (e.g., eyeglasses, visors, gloves, watches, wristbands, etc.). For example, object tracking can be implemented for recognizing certain user gestures, such as head nods or shakes, eye winks or other ocular motion, or hand and/or finger gestures, as input for the device. Object tracking can also be utilized for advanced device security features such as ensuring “live” facial recognition, fingerprinting, retinal scanning, or identification based on gait. Devices capable of object tracking can also be configured for video editing techniques such as video stabilization (e.g., to remove jitter) or to render smooth camera motions due to panning, tilting, or dollying in/dollying out. Object tracking, however, can be challenging because of abrupt motion of the tracked object(s), changes in appearance of the tracked object(s) and background, non-rigidity of the tracked object(s), and device motion. In addition, factors such as image sensor and lens characteristics, illumination conditions, noise, and occlusion can also affect how an object is represented from image to image or frame to frame. Further, the requirements of real-time processing can often be at odds with the objective of minimizing processing and power use on portable computing devices.